#pragma once
#include "pasex.hh"
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

namespace parse
{
	struct symbol
	{
		symbol() {}
		symbol(std::string s);

		bool terminal = false;
		bool mark = false;
		bool start = false;
		std::string s;
	};

	std::istream & operator>>(std::istream & is, symbol & s);
	bool operator<(symbol const & a, symbol const & b);
	bool operator==(symbol const & a, symbol const & b);

	struct context_free_rule
	{
		context_free_rule() {}
		context_free_rule(symbol const& lhs, std::vector<symbol> const& rhs);

		symbol lhs;
		std::vector<symbol> rhs;
	};

	std::istream & operator>>(std::istream & is, context_free_rule & rp);
	bool operator<(context_free_rule const & a, context_free_rule const & b);
	bool operator==(context_free_rule const & a, context_free_rule const & b);


	struct context_free_grammar
	{
		void get_first(symbol const& u, symbol const& start);
		int index(symbol const& s);
		void add_first_edge(symbol const& u, symbol const& v);
		void build_first_graph();
		void init_lead_empty();
		void init();
		void push(context_free_rule const & rp);
		bool lead_empty(symbol const & s) const;
		std::set<symbol> first_of_symbols(std::vector<symbol> const & sys, std::set<symbol> const & lookahead) const;

		std::set<char> alpha;
		std::set<symbol> all_symbol;
		std::set<symbol> lefts;
		std::set<symbol> vis;
		std::set<symbol> lead_empty_symbol;
		std::map<symbol, std::set<symbol>> first;
		std::multimap<symbol, context_free_rule> rps;
		std::vector<std::vector<symbol>> first_graph;
		std::map<symbol, int> symbol_index;
		int alloc = 0;
		bool start_empty = false;
		symbol start;
		symbol start_ex;
	};

	std::istream & operator>>(std::istream & is, context_free_grammar & cfg);

	struct ex_context_free_rule
	{
		ex_context_free_rule() {}
		ex_context_free_rule(context_free_rule cfr, int point) : r(cfr), point(point)
		{
			if (r.rhs[0].s == "&") r.rhs.clear();
		}

		context_free_rule r;
		int point = 0;
	};

	bool operator<(ex_context_free_rule const & a, ex_context_free_rule const & b);


	struct lr_set_base
	{
		void add(ex_context_free_rule const & ecfr, std::set<symbol> const & ss);
		void add(ex_context_free_rule const & ecfr, symbol const & ch);

		std::map<ex_context_free_rule, std::set<symbol>> lrs;
	};

	struct lr_set
	{
		lr_set() {}
		lr_set(lr_set_base const & lsb, context_free_grammar const & cfg);

		bool in(std::set<symbol> const& a, std::set<symbol> const& b);

		std::map<ex_context_free_rule, std::set<symbol>> lrs;
	};

	bool operator<(lr_set const & a, lr_set const & b);

	struct lr_set_dfa
	{
		lr_set_dfa() {}
		lr_set_dfa(context_free_grammar const & cfg);

		void add_edge(int u, int v, symbol const & s) { graph[u][s] = v; }
		int node_index(lr_set const & ls);
		int alloc_node(lr_set const & ls);
		int rr_conflict_count() const;
		int sr_conflict_count() const;
		int size() const;
		bool acc(int state);
		bool parse(std::string const & s, lex::dfa::dfa & d);
		void print();

		int alloc = 0;
		std::vector<std::map<symbol, int>> graph;
		std::map<lr_set, int> index;
		std::vector<lr_set> all;
	};
}

